package leetcode_1100;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 *@author 周杨 
 *FlowerPlantingWithNoAdjacent_1042 给一个数组有若干[i,j] 表明有条路径i-j是联通的 联通两端必须是不同颜色 一共只有4种颜色 问最终的任意一种答案
 *describe:分组用map记录即可 
 *2019年5月13日 上午13:47
 */
public class FlowerPlantingWithNoAdjacent_1042 {
	public static void main(String[] args) {
		FlowerPlantingWithNoAdjacent_1042 test = new FlowerPlantingWithNoAdjacent_1042();
		int[] res = test.gardenNoAdj(3,new int[][] {{1,2},{2,3},{3,1}});
		System.out.println(res);
	}
	
	public int[] gardenNoAdj(int N, int[][] paths) {
        Map<Integer,Set<Integer>> map = new HashMap<Integer,Set<Integer>>();
        for(int[] path:paths) {
        	if(path[0]<path[1]) {
        		Set<Integer> set = map.getOrDefault(path[1], new HashSet<Integer>());
        		set.add(path[0]);
        		map.put(path[1], set);
        	}else {
        		Set<Integer> set = map.getOrDefault(path[0], new HashSet<Integer>());
        		set.add(path[1]);
        		map.put(path[0], set);
        	}
        }
        int[] res = new int[N];
        for(int i=0;i<N;++i) {
        	boolean[] help = new boolean[4];
        	Set<Integer> set = map.get(i+1);
        	if(set == null) res[i] = 1;
        	else {
        		for(int next:set) {
        			if(!help[res[next-1]-1]) help[res[next-1]-1] = true;
        		}
        		int tmp = 0;
        		while(help[tmp]) ++tmp;
        		res[i] = tmp+1;
        	}
        }
        return res;
    }
}
